package a08_回溯算法;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 将字符串切割成合法的ip地址
 *
 *
 *
 * @author flyduck
 * @since 2025/1/2
 */
public class a10_复原IP地址 {
    public static void main(String[] args) {
        a10_复原IP地址 test = new a10_复原IP地址();
        List<String> aab = test.restoreIpAddresses("0279245587303");
        System.out.println(aab);
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        LinkedList<String> path = new LinkedList<>();
        char[] chars = s.toCharArray();
        traversal(result, path, chars, 0);
        return result;
    }


    private void traversal(List<String> result,
                           LinkedList<String> path,
                           char[] chars,
                           int startIdx){
        if(path.size() == 3){
            if(!isValid(chars, startIdx, chars.length - 1)){
                return;
            }else {
                path.add(splitArray(chars, startIdx, chars.length - 1));
                String ip = path.stream()
                        .collect(Collectors.joining("."));
                path.removeLast();
                result.add(ip);
                return;
            }
        }

        for (int i = startIdx; i < Math.min(startIdx + 4, chars.length); i++) {
            if(!isValid(chars, startIdx, i)){
                continue;
            }
            path.add(splitArray(chars, startIdx, i));
            traversal(result, path, chars, i + 1);
            path.removeLast();
        }
    }

    private boolean isValid(char[] chars,int leftIdx,int rightIdx){
        if(leftIdx > rightIdx){
            return false;
        }
        if(chars[leftIdx] == '0' && leftIdx != rightIdx){
            return false;
        }
        for (int i = leftIdx; i <= rightIdx; i++) {
            if(chars[i] < '0' || chars[i] > '9'){
                return false;
            }
        }

        String s = splitArray(chars, leftIdx, rightIdx);
        if (Long.valueOf(s) > 255) {
            return false;
        }
        return true;
    }

    private String splitArray(char[] chars,int leftIdx,int rightIdx){
        StringBuilder sb = new StringBuilder();
        while (leftIdx <= rightIdx) {
            sb.append(chars[leftIdx]);
            leftIdx++;
        }
        return sb.toString();
    }
}
